
\section{LMT Skeleton}
\label{sec:lmtSkeleton}

\subsection[LMT theory]{The theory behind the LMT skeleton generation algorithm}

\subsection[LMT Implementation]{Implementing the LMT skeleton algorithm} To recap, the goal is to generate a set of edges, known as the LMT skeleton, which are guaranteed to be part of the minimum weight triangulation. The algorithm, on completion, should return a set of edges which all belong to the MWT, and which together form the LMT skeleton.\\\\Initially, a set of nodes which exist in a two dimensional space is used. In this particular case, the nodes are randomly generated within a certain x, y boundary.\\\\
The description of the algorithm from \cite{LargeSubgraph} is as follows:

\footnotesize
\begin{enumerate}

\item \emph{candEdges} := A list of empty edges in $S$

\item \emph{edgesIn} := A new empty list

\item Remove convex hull edges from the \emph{candEdges} list and add them to the \emph{edgesIn} list

\item {\bf REPEAT}
	\begin{enumerate}
	\item  {\bf FOR} each edge $e$ $\in$ $candEdges$ {\bf DO}:
	
		 {\bf IF} there does not exist a pair of triangle $t_i$ $\in$ $T_L(e)$ and $t_j$ $\in$ $T_R(e)$ such that $e$ is locally minimal with respect to $t_i$ and $t_j$, and $t_i$ and $t_j$ are both in $candTris$, {\bf THEN} remove $e$ from $candEdges$ and remove all triangles containing $e$ from $candTris$.
		 
 		{\bf END FOR}
  
  
  	 \item  {\bf FOR} each edge $e$ $\in$ $candEdges$ {\bf DO}:
	 
   		  {\bf IF} $e$ intersects no other edge in $candEdges$, {\bf THEN} add $e$ to the $edgesIn$.
   		 
		 {\bf END FOR}
  	 \end{enumerate}

   {\bf UNTIL no more edges change status}
\end{enumerate}
\normalsize
The initial version of the algorithm, was implemented based off the above pseudo-code. The method described here did not attempt to optimize the algorithm for speed or use complex data structures, but only to serve as a simple demonstration of the algorithm. Later implementations added various optimizations, and data structures that made the code more efficient.\\\\
The key parts of the implementation in Java are listed below. The algorithm runs in three parts - first of all, there is an initialization and generation stage (referred to as stage A). This is followed by a loop that contains two inner loops, stage B and C.\\\\
The stage A of the algorithm is as follows:
\begin{lstlisting}[caption=Initialisation phase of the LMT Skeleton Algortihm]{Name}
	set.generateTriangles(); // The IndexedFaceSet contains the points
	
	List<Edge> edgesIn = ConvexHullCreator.getHullEdges(set.getCandidateEdges());
	
	for (Edge e:edgesIn) {
		set.removeEdgeButLeaveTriangles(e);
	}
	
	DoublyLinkedList<Edge> edges = set.getCandidateEdges();
	do {
		edgeChanged = false;
			
		// INNERLOOP A runs here
			
		// INNERLOOP B runs here
		
	} while (edgeChanged);
\end{lstlisting}
Within the outer loop, there are two sub loops being run. The first loop A eleminates a number of edges if they are not locally minimal for any triangulation.
\begin{lstlisting}[caption=Inner Loop A of the Simple LMT Skeleton Algortihm]{Name}
	for (Edge edge : edges) {
		set.removeNonEmptyTrianglesForEdge(edge);
		if  ( ! edge.isDiagonalOfQuadrilateral() ) {
			continue;
		}
				
		if ( ! metric.localMinimumExistsForEdge(edge, set) ) {
			set.removeEdge(edge);
			edgeChanged = true;
	 	} 
	}
\end{lstlisting}
The second loop B then selects the valid edges for the MWT
\begin{lstlisting}[caption=Inner Loop B of the Simple LMT Skeleton Algortihm]{Name}
	for (Edge edge : edges) {
		boolean intersects = false;
		for (Edge otherEdge: set.getCandidateEdges()) {
					
			if (! edge.isAdjacentToEdge(otherEdge)) {
				if (edge != otherEdge && edge.intersects(otherEdge, -0.00001)) {
					intersects = true;
					break;
				}
			}
		}
				
		if (intersects == false) {
			edge.setHighlighted(false);
			edgesIn.add(edge);
			set.removeEdgeButLeaveTriangles(edge); 
			edgeChanged = true;
		}
	}
\end{lstlisting}

To go into the detail of the implementation:\\\\
 {\bf Stage 1}: Triangle generation and convex hull edges
\begin{itemize}
\item In the generation stage, all possible edges between every node within the set are generated, and are added to a list labelled 'candEdges'. This list will always represents all the edges that qualify as candidates to be part of the skeleton. As the algorithm proceeds, edges would be eliminated from the candEdges list.

\item Every edge can form a triangle with any other point that exists within the set of points. The next step involves generating a list of triangles from each edge to every other point. For example, an edge with two endpoints A and B can form a triangle with another random point C that exists within the set. The list of these triangles is then stored.

\item Every edge that is on the convex hull of the point set is necessarily part of the LMT skeleton. As such, all  these edges are selected and added to a list $edgesIn$ which will hold all the edges that are in the LMT skeleton. Afterwards, all convex hull edges that do not belong to an existing triangle are removed from the $candEdges$ list.

\item The outer loop, as specified in step 4 above is then executed.\\
\end{itemize}
{\bf Stage 2}: The inner loop A
\begin{itemize}
\item In the first inner loop, all remaining candidate edges are walked through. Each edges has number of triangles that are built around it with other points in the set - only the empty triangles (no points within them) are of interest, so all the other triangles are discarded

\item Every edge needs to have at least two triangles attached to it, implying that the edge needs to the diagonal of a four sided shape, the quadrilateral. All edges that do not fulfill this property are discarded

\item It is then observed if the edge is a valid local minimum for any possible quadrilateral. If it is not part of the local minimum for all quadrilaterals, it cannot be part of the MWT, and so it is not a candidate edge and can be removed from the candidate list. What this means is that the edge is flipped to form two other triangles (by joining the two other points of the quadrilateral), and this flipped state has a lower weight, then it is not minimal within this quad. If for all possible such quads, it is never minimal, it means that this edge cannot be part of the MWT. The edge can then be removed from the candidate edges.

\end{itemize}

{\bf Stage 3}: The inner loop B
\begin{itemize}
\item In the second inner loop, again all edges are walked through. This loop checks through the edges to make sure that they do not intersect with any other edge.
\item Any edge that remains in the candidate Edges, but that does not intersect with any other edge is going to be part of our LMT skeleton. It is then added to the $edgesIn$ collection. If the edge is not part of any triangle, it is removed from the candidate Edges.
\item The $edgesChanged$ variable is used to indicate if items were removed or added from the collections. If there was no change in both inner loops, then the outer loop is aborted, otherwise the outer loop runs again
\end{itemize}
These three stages represent the implementation of the core algorithm in a straightforward and non-optimized manner in the Java programming language. In further development, optimized data structures are used to make the algorithm run more efficiently. This is detailed in the next chapter.